package exercises.leetcode;

/**
 * <a href="https://leetcode-cn.com/problems/trapping-rain-water/">
 * 42. 接雨水</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * <img src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/10/22/rainwatertrap.png">
 * <p>
 * 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
 * 输出：6
 * 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
 * <p>
 * 示例 2：
 * <p>
 * 输入：height = [4,2,0,3,2,5]
 * 输出：9
 *  
 * <p>
 * 提示：
 * <li>n == height.length</li>
 * <li>1 <= n <= 2 * 104</li>
 * <li>0 <= height[i] <= 105</li>
 *
 * @author or2
 * @date 2021年10月04日 时间: 11:01
 */
public class No42 {
    public int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int leftHeight = height[0], rightHeight = height[right];

        int res = 0;
        while (left <= right) {
            if (leftHeight > rightHeight) {
                res += rightHeight - height[right];
                rightHeight = Math.max(height[--right], rightHeight);
            } else {
                res += leftHeight - height[left];
                leftHeight = Math.max(height[++left], leftHeight);
            }
        }

        return res;
    }
}
